﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Recursives
{
    class TreeTest
    {
        public static void Test()
        {
            RecursiveTraverse(Node.BuildTree());
            StackTraverse(Node.BuildTree());
        }

        private class Node
        {
            public Node Left { get; set; }

            public Node Right { get; set; }

            public int Value { get; set; }

            public static Node BuildTree()
            {
                return new Node
                {
                    Value = 1,
                    Left = new Node
                    {
                        Value = 2,
                        Left = new Node
                        {
                            Value = 3
                        },
                        Right = new Node
                        {
                            Value = 4
                        }
                    },
                    Right = new Node
                    {
                        Value = 5,
                        Left = new Node
                        {
                            Value = 6
                        },
                        Right = new Node
                        {
                            Value = 7
                        }
                    }
                };
            }
        }

        private static void RecursiveTraverse(Node node)
        {
            if (node == null)
            {
                return;
            }

            RecursiveTraverse(node.Left);
            Console.WriteLine(node.Value);
            RecursiveTraverse(node.Right);
        }

        private enum CodeAddress
        {
            Start,
            AfterFirstRecursiveCall,
            AfterSecondRecursiveCall
        }

        private class StackFrame
        {
            public Node Node { get; set; }

            public CodeAddress CodeAddress { get; set; }
        }

        private static void StackTraverse(Node node)
        {
            var stack = new Stack<StackFrame>();
            stack.Push(new StackFrame
            {
                Node = node,
                CodeAddress = CodeAddress.Start
            });

            while (stack.Count > 0)
            {
                var current = stack.Peek();

                switch (current.CodeAddress)
                {
                    case CodeAddress.Start:
                        if (current.Node == null)
                        {
                            stack.Pop();
                        }
                        else
                        {
                            current.CodeAddress = CodeAddress.AfterFirstRecursiveCall;
                            stack.Push(new StackFrame
                            {
                                Node = current.Node.Left,
                                CodeAddress = CodeAddress.Start
                            });
                        }
                        break;
                    case CodeAddress.AfterFirstRecursiveCall:
                        Console.WriteLine(current.Node.Value);

                        current.CodeAddress = CodeAddress.AfterSecondRecursiveCall;
                        stack.Push(new StackFrame
                        {
                            Node = current.Node.Right,
                            CodeAddress = CodeAddress.Start
                        });
                        break;
                    case CodeAddress.AfterSecondRecursiveCall:
                        stack.Pop();
                        break;
                }
            }
        }
    }
}
